/**
 * Trabalho 2 de COmputacao 2 - 2007/2
 * Grupo:
 * 	Anderson Marinho
 * 	Artur Barbalho
 * 
 */

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

template<class T> class exp {
public:
	virtual T executa() const = 0;
};

template<class T> class myList;

template<class T> class var : public exp<T> {
protected:
	T v;
public:
	var() :
		v() {
	}
	var(const T& _v) :
		v(_v) {
	}
	virtual T executa() const {
		return v;
	}

	var<T>& operator =(T _v) {
		v = _v;
		return *this;
	}
};

template<class T> class myList {
private:
	vector<T> v;
public:

	myList() {

	}

	myList(const vector<T>& _v) :
		v(_v) {
	}

	void push_back(const T& x) {
		v.push_back(x);
	}

	void clear() {
		v.clear();
	}

	typename vector<T>::iterator insert(typename vector<T>::iterator pos,
			const T& x) {
		return v.insert(pos, x);
	}

	typename vector<T>::iterator erase(typename vector<T>::iterator pos) {
		return v.erase(pos);
	}

	typename vector<T>::iterator begin() {
		return v.begin();
	}

	typename vector<T>::iterator end() {
		return v.end();
	}

	typename vector<T>::reference front() {
		return v.front();
	}

	int size() {
		return v.size();
	}

	virtual vector<T> executa() const {
		return v;
	}

	myList<T>& operator =(const vector<T> _v) {
		clear();
		for (typename vector<T>::const_iterator j = _v.begin(); j != _v.end(); ++j ) {
			push_back(*j);
		}
		return *this;
	}

};

template<class T> class cte : public exp<T> {
private:
	T v;
public:
	cte() {
	}
	cte(T v) :
		v(v) {
	}
	virtual T executa() const {
		return v;
	}
};

template<class T, class X> class Funcao1 : public exp<T> {
private:
	T (*func)(X);
	const exp<X> *p1;
public:
	Funcao1(T (*func)( X ), const exp<X> *p1) :
		func(func), p1(p1) {
	}
	virtual T executa() const {
		return func(p1->executa());
	}
};

template<class T, class X1, class X2> class Funcao2 : public exp<T> {
private:
	T (*func)(X1, X2);
	const exp<X1> *p1;
	const exp<X2> *p2;
public:
	Funcao2(T (*func)( X1,X2 ), const exp<X1> *p1, const exp<X2> *p2) :
		func(func), p1(p1), p2(p2) {
	}
	virtual T executa() const {
		return func(p1->executa(), p2->executa());
	}
};

template<class T, class X1, class X2, class X3> class Funcao3 : public exp<T> {
private:
	T (*func)(X1, X2, X3);
	const exp<X1> *p1;
	const exp<X2> *p2;
	const exp<X3> *p3;
public:
	Funcao3(T (*func)( X1,X2,X3 ), const exp<X1> *p1, const exp<X2> *p2,
			const exp<X3> *p3) :
		func(func), p1(p1), p2(p2), p3(p3) {
	}
	virtual T executa() const {
		return func(p1->executa(), p2->executa(), p3->executa());
	}
};

template<class X, class Y, class T> class oper2 : public exp<T> {
protected:
	const exp<X> *a;
	const exp<Y> *b;
	oper2(const exp<X> * a, const exp<Y> * b) :
		a(a), b(b) {
	}
public:
	const exp<X> * getA() const {
		return a;
	}
	const exp<Y> * getB() const {
		return b;
	}
};

template<class X, class Y, class T> class soma : public oper2<X,Y,T> {
public:
	soma(const exp<X> * a, const exp<Y> * b) :
		oper2<X, Y, T>(a, b) {
	}
	virtual T executa() const {
		return oper2<X,Y,T>::a->executa() + oper2<X,Y,T>::b->executa();
	}
};

template<class X, class Y, class T> class subtrai : public oper2<X,Y,T> {
public:
	subtrai(const exp<X> * a, const exp<Y> * b) :
		oper2<X, Y, T>(a, b) {
	}
	virtual T executa() const {
		return oper2<X,Y,T>::a->executa() - oper2<X,Y,T>::b->executa();
	}
};

template<class X, class Y, class T> class multiplica : public oper2<X,Y,T> {
public:
	multiplica(const exp<X> * a, const exp<Y> * b) :
		oper2<X, Y, T>(a, b) {
	}
	virtual T executa() const {
		return oper2<X,Y,T>::a->executa() * oper2<X,Y,T>::b->executa();
	}
};

template<class X, class Y, class T> class divide : public oper2<X,Y,T> {
public:
	divide(const exp<X> * a, const exp<Y> * b) :
		oper2<X, Y, T>(a, b) {
	}
	virtual T executa() const {
		return oper2<X,Y,T>::a->executa() / oper2<X,Y,T>::b->executa();
	}
};

template<class T> class modulo : public oper2<T,T,T> {
public:
	modulo(const exp<T> * a, const exp<T> * b) :
		oper2<T, T, T>(a, b) {
	}
	virtual T executa() const {
		return oper2<T,T,T>::a->executa() % oper2<T,T,T>::b->executa();
	}
};

template<class T> class igual : public oper2<T,T,bool> {
public:
	igual(const exp<T> * a, const exp<T> * b) :
		oper2<T, T, bool>(a, b) {
	}
	virtual bool executa() const {
		return oper2<T,T,bool>::a->executa() == oper2<T,T,bool>::b->executa();
	}
};

template<class T> class maior : public oper2<T,T,bool> {
public:
	maior(const exp<T> * a, const exp<T> * b) :
		oper2<T, T, bool>(a, b) {
	}
	virtual bool executa() const {
		return oper2<T,T,bool>::a->executa() > oper2<T,T,bool>::b->executa();
	}
};

template<class T> class maiorIgual : public oper2<T,T,bool> {
public:
	maiorIgual(const exp<T> * a, const exp<T> * b) :
		oper2<T, T, bool>(a, b) {

	}
	virtual bool executa() const {
		return oper2<T,T,bool>::a->executa() >= oper2<T,T,bool>::b->executa();
	}
};

class _and : public oper2<bool,bool,bool> {
public:
	_and(const exp<bool> * a, const exp<bool> * b) :
		oper2<bool, bool, bool>(a, b) {
	}
	virtual bool executa() const {
		return oper2<bool,bool,bool>::a->executa()
				&& oper2<bool,bool,bool>::b->executa();
	}
};

class _or : public oper2<bool,bool,bool> {
public:
	_or(const exp<bool> * a, const exp<bool> * b) :
		oper2<bool, bool, bool>(a, b) {
	}
	virtual bool executa() const {
		return oper2<bool,bool,bool>::a->executa()
				&& oper2<bool,bool,bool>::b->executa();
	}
};

template<class T> ostream& operator <<(ostream& o, const vector<T>& v) {
	bool first = true;
	o << "[";
	for (typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i ) {
		o << (first ? "" : ",")<< *i;
		first = false;
	}
	o << "]";
	return o;
}

template<class T> ostream& operator <<(ostream& o, const myList<T>& _v) {
	return o << _v.executa();
}

_and operator &&(const exp<bool>& a, const exp<bool>& b) {
	return _and(&a, &b);
}

_or operator ||(const exp<bool>& a, const exp<bool>& b) {
	return _or(&a, &b);
}

template<class T> igual<T> operator ==(const exp<T>& a, const exp<T>& b) {
	return igual<T>(&a, &b);
}

template<class T> igual<T> operator ==(const exp<T>& a, const T b) {
	return igual<T>(&a, new cte<T>(b));
}

template<class T> maior<T> operator >(const exp<T>& a, const exp<T>& b) {
	return maior<T>(&a, &b);
}

template<class T> maior<T> operator <(const exp<T>& a, const exp<T>& b) {
	return maior<T>(&b, &a);
}

template<class T> maiorIgual<T> operator >=(const exp<T>& a, const exp<T>& b) {
	return maiorIgual<T>(&a, &b);
}

template<class T> maiorIgual<T> operator <=(const exp<T>& a, const exp<T>& b) {
	return maiorIgual<T>(&b, &a);
}

template<class T> modulo<T> operator %(const exp<T>& a, const exp<T>& b) {
	return modulo<T>(&a, &b);
}

template<class T> modulo<T> operator %(const exp<T>& a, const T b) {
	return modulo<T>(&a, new cte<T>(b));
}

template<class X, class Y> soma<X,Y,X> operator +(const exp<X>& a,
		const exp<Y>& b) {
	return soma<X, Y, X>(&a, &b);
}

template<class X, class Y> subtrai<X,Y,X> operator -(const exp<X>& a,
		const exp<Y>& b) {
	return subtrai<X, Y, X>(&a, &b);
}

template<class X> soma<X,myList<X>,myList<X> > operator +(const exp<X>& a,
		const exp<myList<X> >& b) {
	return soma<X, myList<X>, myList<X> >(&a, &b);
}

template<class X, class Y> multiplica<X,Y,X> operator *(const exp<X>& a, const exp<Y>& b) {
	return multiplica<X,Y,X>(&a, &b);
}

template<class X, class Y> divide<X,Y,X> operator /(const exp<X>& a, const exp<Y>& b) {
	return divide<X,Y,X>(&a, &b);
}

template<class T> myList<T> operator +(const T& x, const myList<T>& y) {
	myList<T> resp(y.executa());
	resp.insert(resp.begin(), x);
	return resp;
}

template<class T> myList<T> operator +(const myList<T>& y, const T& x) {
	myList<T> resp(y.executa());
	resp.push_back(x);
	return resp;
}

/*
 template<class T> myList<T> operator +(const vector<T>& x, const vector<T>& y) {
 vector<T> resp(x);
 //	cout << "x:" << x << endl;
 //	cout << "y:"<< y << endl;
 for (typename vector<T>::const_iterator i = y.begin(); i != y.end(); i++) {
 resp.push_back(*i);
 }
 return resp;
 }*/

/*
 template<class T> myList<T> operator +(myList<T> x, myList<T> y) {
 return x.executa() + y.executa();
 }*/

template<class X, class Y, class W> myList<W> apply(var<X>& x,
		const exp<myList<X> >& _vx, var<Y>& y, const exp<myList<Y> >& _vy,
		const exp<W>& e, const exp<bool>& condicao) {
	myList<W> result;
	myList<X> vx = _vx.executa();
	myList<Y> vy = _vy.executa();
	for (typename vector<X>::const_iterator i = vx.begin(); i != vx.end(); ++i ) {
		x = *i;
		for (typename vector<Y>::const_iterator j = vy.begin(); j != vy.end(); ++j ) {
			y = *j;
			if (condicao.executa())
				result.push_back(e.executa() );
		}
	}
	return result;
}

template<class X, class Y, class W> myList<W> apply(var<X>& x,
		const exp<myList<X> >& vx, var<Y>& y, const exp<myList<Y> >& vy,
		const exp<W>& e) {
	return apply(x, vx, y, vy, e, cte<bool>(true));
}

template<class X, class W> myList<W> apply(var<X>& x,
		const exp<myList<X> >& _v, const exp<W>& e, const exp<bool>& condicao) {
	myList<W> result;
	myList<X> v = _v.executa();
	for (typename vector<X>::const_iterator i = v.begin(); i != v.end(); ++i ) {
		x = *i;
		if (condicao.executa() )
			result.push_back(e.executa() );
	}

	return result;
}

template<class T, class W> myList<W> apply(var<T>& x, const exp<myList<T> >& v,
		const exp<W>& e) {
	return apply(x, v, e, cte<bool>(true));
}

template<class T> myList<T> I(const T& a, const T& b) {
	myList<T> l;
	l.push_back(a);
	l.push_back(b);
	return l;
}

myList<int> I(int a, int b) {
	myList<int> l;
	for (int i = a; i <= b; i++)
		l.push_back(i );
	return l;
}

template<class T> struct C1 {
	const exp<myList<T> > * l;
	C1(const exp<myList<T> > * l) :
		l(l) {
	}
};

template<class T> struct C2 {
	const exp<myList<T> > * l;
	var<T>& _var;
	C2(var<T>& _var, const exp<myList<T> >* l) :
		_var(_var), l(l) {
	}
};

template<class T, class W> struct C3 {
	const exp<myList<T> > * l;
	var<T>& _var;
	const exp<W>& e;
	C3(const exp<W>& e, var<T>& _var, const exp<myList<T> >* l) :
		e(e), _var(_var), l(l) {
	}
};

template<class T, class W> struct C4 {
	const exp<myList<T> > * l;
	var<T>& _var;
	const exp<W>& e;
	const exp<bool>& condicao;
	C4(const exp<W>& e, var<T>& _var, const exp<myList<T> >* l,
			const exp<bool>& condicao) :
		e(e), _var(_var), l(l), condicao(condicao) {
	}
};

template<class X, class Y, class Z> struct C5 {
	const exp<myList<X> > * l1;
	var<X>& var1;
	const exp<myList<Y> > * l2;
	var<Y>& var2;
	const exp<Z>& e;
	C5(const exp<Z>& e, var<X>& var1, const exp<myList<X> >* l1, var<Y>& var2,
			const exp<myList<Y> >* l2) :
		e(e), var1(var1), l1(l1), var2(var2), l2(l2) {
	}
};

template<class X, class Y, class Z> struct C6 {
	const exp<myList<X> > * l1;
	var<X>& var1;
	const exp<myList<Y> > * l2;
	var<Y>& var2;
	const exp<Z>& e;
	const exp<bool>& condicao;
	C6(const exp<Z>& e, var<X>& var1, const exp<myList<X> > * l1, var<Y>& var2,
			const exp<myList<Y> > * l2, const exp<bool>& condicao) :
		e(e), var1(var1), l1(l1), var2(var2), l2(l2), condicao(condicao) {
	}
};

template<class T> C1<T> operator -(const exp<myList<T> >& l) {
	return C1<T>(&l);
}

template<class T> C1<T> operator -(const myList<T> l) {
	return C1<T>(new cte<myList<T> >(l));
}

template<class T> C2<T> operator <(var<T>& _var, const C1<T>& c1) {
	return C2<T>(_var, c1.l);
}

template<class T> C2<myList<T> > operator <(myList<T>& _var,
		const C1<myList<T> >& c1) {
	var<myList<T> > v(_var);
	return C2<myList<T> >(v, c1.l);
}

template<class T, class W> C3<T,W> operator |(const exp<W>& e, const C2<T>& c) {
	return C3<T, W>(e, c._var, c.l);
}

template<class T, class W> C3<myList<T>,myList<W> > operator |(
		const myList<W>& e, const C2<myList<T> >& c) {
	return C3<myList<T>, myList<W> >(cte<myList<W> >(e), c._var, c.l);
}

template<class T, class W> C4<T,W> operator ,(const C3<T,W>& c,
		const exp<bool>& condicao) {
	return C4<T, W>(c.e, c._var, c.l, condicao );
}

template<class X, class Y, class Z> C5<X,Y,Z> operator ,(const C3<X,Z>& c,
		const C2<Y>& y) {
	return C5<X, Y, Z>(c.e, c._var, c.l, y._var, y.l);
}

template<class X, class Y, class Z> C6<X,Y,Z> operator ,(const C5<X,Y,Z>& c,
		const exp<bool>& condicao) {
	return C6<X, Y, Z>(c.e, c.var1, c.l1, c.var2, c.l2, condicao);
}

struct ZF {
	template<class T, class W> myList<W> operator [](const C3<T,W>& c) {
		return apply<T, W>(c._var, *(c.l), c.e);
	}
	template<class T, class W> myList<W> operator [](const C4<T,W>& c) {
		return apply<T, W>(c._var, *(c.l), c.e, c.condicao);
	}
	template<class X, class Y, class Z> myList<Z> operator [](const C5<X,Y,Z>& c) {
		return apply<X, Y, Z>(c.var1, *(c.l1), c.var2, *(c.l2), c.e);
	}
	template<class X, class Y, class Z> myList<Z> operator [](const C6<X,Y,Z>& c) {
		return apply<X, Y, Z>(c.var1, *(c.l1), c.var2, *(c.l2), c.e, c.condicao);
	}
} zf;

template<bool (*func)( int )> Funcao1<bool,int> call(const exp<int>& p1) {
	return Funcao1<bool, int>(func, &p1 );
}

template<myList<myList<int> > (*func)( int )> Funcao1<myList<myList<int> >,int> call(const int p1) {
	return Funcao1<myList<myList<int> >, int>(func, new cte<int>(p1));
}

template<bool (*func)( int, myList<int>, int )> Funcao3<bool,int,myList<int>,int > call(
		const exp<int>& p1, const exp<myList<int> >& p2, const int p3) {
	return Funcao3<bool, int, myList<int>, int>(func, &p1, &p2, new cte<int>(p3));
}

/* Em haskell

 boardSize = 8
 queens 0 = [[]]
 queens n = [ x : y | y <- queens (n-1), x <- [1..boardSize] , safe x y 1]
 safe x [] n = True
 safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]

 */

bool safe(int x,myList<int> y, int n) {
	if (y.size() == 0)
		return true;
	else {
		int c = y.front();
		y.erase(y.begin());
		return (x != c) && (x != c+n) && (x != c-n) && safe(x, y, n+1);
	}
}

myList< myList< int > > queens(int n) {
	if (n == 0) {
		myList<int> empty;
		myList<myList< int > >ret;
		ret.push_back(empty);
		return ret;
	} else {
		var<int> x;
		var<myList<int> >y;
		return zf[x+y | y <- queens(n-1), x<-I(1,8), call<safe>(x, y, 1 ) ];
	}
}

bool par(int n) {
	return !(n % 2);
}

int main(int argc, char *argv[]) {
	var<int> x, y=1;
	var<int> w = 2;
	var< myList<int> > z;
	//call<safe>(x, z, 0);
	cout << zf[ x*x | x <- I(0,10), call<par>( x )]<< endl;
	cout << zf[ x/x | x <- I(1,10), x%2==0]<< endl;//tudo 1
	cout << zf[ x+x | x <- I(0,10), call<par>( x )]<< endl;
	cout << zf[ x-x | x <- I(1,10), x%2==0]<< endl;//tudo 0
	//cout << zf[ x | x <- (I(0,10)+I(1,3))]<< endl;
	//cout << zf[ z | z <- I(I(0,2),I(10,16))]<< endl;
	myList<myList<int> > v;
	//cout << zf[x+z| z <- v, x<-I(1,8) ] << endl;
	igual<int > _i(&x, &x);
	//cout << _i.depende((void*)&x) << endl; //imprime 1
	//cout << _i.depende((void*)&y) << endl; //imprime 0
	//cout << _myList.depende()
	//cout << zf[y | x<-I(1,2), w<-I(1,2)] << endl;//imprime 1 elemento
	//cout << zf[y | x<-I(1,2), w<-I(1,2), x == x] << endl;//imprime 2 elementos
	//cout << zf[x | x<-I(1,2)] << endl;
	//myList<myList<int> > l = I(I(0,2),I(10,16));
	//cout << l << endl;
	cout << queens(8) << endl;
	//system("pause");
	return EXIT_SUCCESS;
}
